演算法課程
演算法課程
(Algorithms)
(Algorithms)
國立聯合大學
國立聯合大學
資訊管理學系
資訊管理學系
陳士杰老師
陳士杰老師
Course 9
NP Theory序論
An Introduction to the Theory of NP
2
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Outlines
本章重點
Polynomial Time
Intractability
Optimization Problems vs. Decision Problems
The Theory of NP
{ P problem
{ NP problem
{ NP-complete problem
{ NP-hard problem
如何証明某個問題為NP-complete問題
近似演算法
3
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Polynomial Time (多項式時間)
什麼是
多項式時間
多項式時間
(Polynomial Time)
(Polynomial Time)”?
Polynomial
Polynomial
Time
Time
Non
Non
-
-
Polynomial
Polynomial
Time
Time
4
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Def
Def:
一個稱為多項式時間的演算法(
Polynomial
Polynomial
-
-
time Algorithm
time Algorithm)
須符合:在合理的輸入大小 (input size)下,該演算法於最差情況
(Worst-case)的時間複雜度以多項式函數為限。
因此,若ninput size,存在一個多項式函數
p
(
n
) ,則:
Polynomial
Polynomial
-
-
time computable
time computable
一函數 f(x) polynomial-time computable,若且為若存在一演算
法,使得對所有的輸入 x,皆可在Polynomial Time內求得 f
5
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
如果我們講「這個問題很難」,這句話可能有兩種不同的
意義:
[意義 1]: 這個問題也許目前已經有一些還不錯的近似解法,只是想
進一步找出真正最佳的方法是件困難的事
[意義 2]: 這個問題本身就難以找出解決方法。
第一種意思指的是對
而言很困難,而第二種意思指的是
計算機
計算機而言很難。
在探討問題的難度時,比較正確的講法應該是指一個問題
易解的
易解的
(tractable)
(tractable) 或是
難解的
難解的
(intractable)
(intractable)
Intractability (難解問題)
6
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
在資訊科學領域中,若無法在最差情況(Worst-case)下,以多項式時間
的演算法來解決某個問題,該問題就被稱為難解 (Intractable)問題。
一個難解的問題,必須沒有任何多項式時間的演算法可以解它。
但是,如果有一個問題在最差情況(Worst-case)下,目前還找不到一個
Polynomial-Time Algorithm解它,但是也無法保証未來就找不到
Polynomial-Time Algorithm來解這個問題,則
無法証明
無法証明
該問題是
該問題是
Intractable
Intractable
.
For example:
{ 早期,利用
brute
brute
-
-
force algorithm (
force algorithm (
暴力演算法
暴力演算法
)
) 解連鎖矩陣相乘問題
(Chained Matrix Multiplication problem) ,其時間複雜度為
non
non
-
-
polynomial
polynomial
time
time.
{ 然而,若以
dynamic programming algorithm
dynamic programming algorithm (Algorithm 3.6) 來解,則其
時間複雜度為
Θ
Θ
(
(
n
n
3
3
)
).
7
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
就難解性而言,問題的主要分類可分為三種:
Problems for which polynomial-time algorithms
have been found
have been found
{ 如:最短路徑問題、MST問題、排序問題、搜尋問題
Problems that have been proven to be
intractable
intractable
{ 時間複雜度被証明為
指數複雜度
指數複雜度
(
(
以上
以上
)
)的問題。如:河內塔問題
{
{
不存在有解決問題之演算法
不存在有解決問題之演算法的問題。如:程式停止問題 (Halting
Problem)、功能相等問題(Equivalence Problem)…
Problems that have not been proven to be intractable, but for which
polynomial-time algorithms have never been found
大多數的問題不是落在第一類,就是落在第三類。
第三類問題中,頗具知名度的是
旅行推銷員問題
旅行推銷員問題
(Traveling
(Traveling
Salesman Problem)
Salesman Problem)
8
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The Traveling Salesman Problem; TSP
9
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
TSP問題:
一個銷售員會不斷地花費時間去拜訪n個城市。(A salesman spends
his time visiting
n
cities cyclically. )
在一趟的旅程中,他只會拜訪每一個城市一次,而且當他回到原
本的起始城市後就會停止此趟的拜訪旅程。(In one tour he visits
each city exactly once, and finishes up where he started.)
什麼樣的拜訪旅程會使該銷售員所花費的旅行距離(成本)最少?
(In what order should he visit the cities to minimize the distance
traveled?)
10
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
若採用暴力法去解TSP問題,則會發現要找出所有可能的
路徑所花費的時間是呈
指數
指數
(Exponentially)
(Exponentially) 成長!!
3 cities Æ 1 solution.
10 cities Æ 181,440 possible tours
n cities Æ (n-1)!/2 possible tours
11
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
n=26,則有 25! /2條不同路徑:
25!=155112100433309859840000001.55 x 10
25
這個數字寫來輕鬆,
究竟有多大?
假設電腦每秒可計算 10
6
條路徑的成本,一年有 3.15 x 10
7
秒, 故一
年可計算 3.15 x 10
13
條路徑,求出所有路徑的成本需時
即便是對不太大的 n=26,就需時五千億年,顯然這種方法毫無用
處。
12
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
在所有的問題當中,除了過去所討論過的各種最
佳化問題 (Optimization Problem) 以外,尚有另外
一種型態的問題:
決策問題
決策問題
(Decision Problem)
(Decision Problem)
Decision Problem
Decision Problem: 此類問題輸出的答案非常簡單,就
yes
yes
no
no兩者之一。
Optimization Problem vs. Decision Problem
13
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The partition problem (分割問題):
給予一組正整數的集合S={a
1
, a
2
, … , a
n
},問: 是否可以將其分割成
個子集合S
1
S
2
,而此兩個子集合的個別總和相等
Ex: Let S = {13, 2, 17, 20, 8}. The answer to this problem instance is "
yes
yes"
because we can partition S into S
1
= {13, 17} and S
2
= {2, 20, 8}.
The Sum of Subset Problem (部份集合的和問題):
給予一組正整數的集合S={a
1
, a
2
, … , a
n
}及一個常數c,問: 集合S中是
否存在一組子集合S’
,此子集合S’數字總合為c
Ex: Let
S
= {12, 9, 33, 42, 7, 10, 5} and
c
= 24.
{ The answer of this problem instance is "
yes
yes" as there exists
S’
= {9, 10, 5}
and the sum of the elements in
S’
is equal to 24.
{ If
c
is 6, the answer will be "
no
no".
14
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The Satisfiability Problem (滿足問題; SAT):
給一個布林函數E,我們對存在於此函數E中的一些變數分別指派True
False,使這個函數結果為True
Ex: Let E = (-x
1
x
2
-x
3
)(x
1
-x
2
) (x
2
x
3
). Then the following assignment
will make E true and the answer will be “
yes
yes”.
x
1
F, x
2
F, x
3
T
If E is -x
1
x
1
, there will be no assignment which can make E true and the
answer will be “
no
no”.
此問題為第一個被証明是屬於
NP
NP
-
-
Complete
Complete的問題 (by S. A. Cook, 1971).
The Minimal Spanning Tree Problem (最小擴張樹問題):
Given a graph G, find a spanning tree T of G with
the minimum length
the minimum length.
15
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The Traveling Salesperson Problem (旅行推銷員問題):
給予一個圖G = (V,E) ,找出一個由該圖的某一點出發所構成的
cycle,此cycle會經過該圖中的每個點一次而再回到出發點,同時
總長度為最短
Ex: Consider following graph. There are two cycles satisfying our
condition. They are C
1
= abedcfaand C
2
= acbe
dfa. C
1
is
shorter
shorter and is the solution of this problem instance.
16
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Some problems:
The Partition Problem
The Partition Problem
The Sum of Subset Problem
The Sum of Subset Problem
The Satisfiability Problem
The Satisfiability Problem
The Minimal Spanning Tree Problem
The Minimal Spanning Tree Problem
The Traveling Salesperson Problem
The Traveling Salesperson Problem
一般來說,最佳化問題(Optimization Problems)
決策問題(Decision Problems)要來得難處理!!
(Decision Problems)
(Decision Problems)
(Optimization Problems)
(Optimization Problems)
17
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
最佳化問題均可找出一個與其對應的決策問題
For example (MST Problem):
Given a graph
G
and a constant
c
.
The total length of the spanning tree of the graph
G
is
a
:
{ If
a
a
<
<
c
c
, then the answer is
yes
yes
,
{
{
otherwise
otherwise, its answer is
no
no
.
這個決策版本的最小擴張樹問題,可以稱為最小擴張樹決
策問題(The minimal spanning tree decision problem)
如果要解某個最佳化問題的決策版本(Decision version of the
optimization problem)已經很困難了,則該問題的最佳化版
本一定更難解決。
18
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The Theory of NP
假設你在一個公司上班。有一天,上司叫你去為某
個對公司很重要的問題找出有效率的演算法。
結果,你研究了很長的一段時間,沒有任何進展,
你去找你的上司
我想不出好方法,我可能太笨了!
19
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
我想不出好方法,
因為不可能有這種好方法!
結果,你的上司要開除掉你這個豬頭,並由一個
演算法設計專家來取代你。此時,你很不爽地對他
20
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
你的上司因為你的強辯,很不情願地再給你一段時
間去証實你的話。
結果,你又試了很長的一段時間,還是失敗了!!此刻
的你既無法找出一個有效率的演算法,又無法証明
這樣的演算法是不存在的
你快要被開除了
21
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
此時,你突然想起在聯合資管上演算法課程時,偉
大的杰哥所過的一段話:
世界上很多的電腦科學家正在為旅行推銷員問題(TSP)
找尋一個較有效率的演算法。但是,到目前為止
卻沒有人能發展出一個在最差情況下,時間複雜
度比指數複雜度要來得好TSP演算法。不過,也
沒有人証明出找到這種演算法是不可能的
22
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
你找到了一線生機!! 因為,你只要能証明找出公司
問題之有效率演算法的難度找出旅行推銷員問
題的有效率演算法
一樣難
一樣難 (亦即:兩者是同一
類的問題),代表著上司要求你解決的問題也曾難
倒很多電腦科學家。
(你很慶幸有好好上演算法)
你終於証明出來公司的問題和旅行推銷員問題是
同一等級的…
23
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
我想不出好方法,
因為這些名人專家也不會!
你被加薪了,因為你讓公司節省了許多經費。
24
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
思考:
Computer Science對於電腦所處理之問題的難易區分標準為何?
將一個問題歸類(轉化)為某一個已知問題的概念與作法為何?
証明一些問題很難為何這麼重要?
以下課程內容所討論到的問題,若無特別說明,皆
以“決策版本
”的問題為主
25
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
除了不存在有解決問題之演算法的問題以外,在可以解決
的問題當中,又可以分成 簡單問題 困難問題
類。而問題的難易之分取決於所使用的演算法類型或使用
之計算機器的類型:
所有可解決之問題
合理輸入資料
輸出結果 Yes/No
決定性演算法
(Deterministic Algo.)
非決定性演算法
(Non-deterministic Algo.)
Deterministic v.s. Non-deterministic
26
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Deterministic Algorithm
Deterministic Algorithm (決定性演算法)
{ Def: 這類演算法在做任何事時,該演算法的下一步只有一件
事可以做。(Permitting at most one next move
at any step in a
computation)
{ 是指演算法中每一個步驟的運算都需要被唯一定義,因此
產生
產生
的結果也是唯一
的結果也是唯一
的。
{ 能夠執行決定性演算法的機器,稱為
決定性的機器
決定性的機器
(Deterministic Machine)。電腦就是一種決定性的機器。
由於在此類計算機器運作的演算法在處理問題時,每一步只有一
件事,因此,只要有一個處理器即可,故容易實現。
27
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Non
Non
-
-
deterministic Algorithm
deterministic Algorithm (非決定性演算法)
{ Def: 這類演算法在做任何事時,該演算法的下一步可能會有
無限多件事可以選擇。 (Permitting more than one choice of
next move at some step in a computation)
{ 演算法中每一個步驟的運算無法被唯一定義。
{ 能夠執行非決定性演算法的機器,稱為
非決定性的機器
非決定性的機器 (Non-
deterministic Machine)
由於非決定性演算法在執行時,每一步可能有無限多件事要處
理,故非決定性計算機器需假設
無限多
無限多
個處理器可平行處理
個處理器可平行處理
因此,非決定性計算機器的計算能力比決定性計算機器要強大。
但是,實際上並不存在此種機器。
28
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Non-deterministic Algorithm的執行步驟分成兩個階段:
猜測階段
猜測階段
(Guess)
(Guess)
{ 由於沒有一個既定的程序來從事此階段的猜測工作,因此本階段是
Non-deterministic
{ 對於本階段,我們只知道一件事:
如果一個問題有正確解的話,此階段
一定
一定可以將這個正確解給猜出來;
反之,若該問題沒有正確解的話,則此階段就會
隨便
隨便給解答。
至於猜測階段是怎麼將這個解答給找出來的,我們無從得知(不論所給的
解是否為正確解)
驗証階段
驗証階段
(Verification)
(Verification)
{ 將上一階段所猜出來的結果加以驗証是否為真 (True)
29
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Nondeterministic SAT
以一個具有n個變數之布林函數E之滿足問題 (SAT) 為例:
如果此問題是使用決定性演算法,則時間複雜度為O(2
n
)
如果此問題是使用非決定性演算法,則時間複雜度為O(n)
/* Guess */
for i = 1 to n do
x
i
choice(true, false);
/* Verification */
if E(x
1
, x
2
, … ,x
n
) is true then
success;
else failure;
30
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Polynomial-Time Reducible (多項式時間的轉化)
Def: 若有兩個問題Q1Q2,其解集合分別為L1L2
如果Q1可以多項式時間轉化成Q2 (即:L1
p
L2 Q1
p
Q2),則
{ 存在一個函數 f(x) /*此函數不一定是實質的數學公式,也可能是一個虛的概念或意涵*/
{ 此函數 f(x) polynomial-time computable
{ 該函數 f(x) 使得對所有x而言,xL1 若且唯若 f(x)L2 (xL1 f(x)L2)
這個Reduce的作用類似
歸類
歸類Q1Q2可被視為同一類型的問題。
Q1
L1
Q2
L2
f(x)
所有在L1的元素,經f(x)轉化後必在L2中;而原
本不在L1的元素,經f(x)轉化後則必不在L2
31
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
為何要做Reduce?
Q1 reduce Q2,表示Q1問題可以由處理Q2問題的演算法所解決。
Q1Input
Reduce
Q2Input
Q2Algo.
Q2Output
Reduce
Q1Output
即:f(x)
即:
xL1 f(x)L2
32
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
前述定義隱含一些概念:
Q1問題可以由處理Q2問題的演算法所解決。若Q2問題有一個有效
率的演算法,可以在多項式時間內將Q2問題給解掉,表示Q1問題
也一定可以在多項式時間內被解掉。
因此,函數 f(x) 必須是要
polynomial
polynomial
-
-
time computable
time computable
{ 這是因為解Q1問題的時間相當於 函數f(x)轉換時間 + Q2問題之
演算法的解題時間所構成。
{ 若轉換時間過長,則解Q2問題之演算法就算是再快,也無助於加速
Q1問題之求解。
可表示成 L1 L2 Q1 Q2
33
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Q1 Q2的意義:
Q2問題比Q1問題難 (雖然兩者是同一類型的問題)
Q2有解,則Q1就有解
想要証明Q1Q2一樣難,則需証出Q1
p
Q2 Q2
p
Q1
Q1 Q2Q2 Q3,則Q1 Q3 (遞移性)
範例:假設現在有下列兩個問題:
Q1: 一台電梯中有4個人,其中是否有三個人彼此互相認識?
Q2:有一個4個頂點之無向圖G=(V,E),其中是否存在一個三角形?
証明Q1
Q2
34
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
解:
有一個函數f,使得:
{
i
→頂vi
{
i
和人
j
互相認識 (vi, vj)E
{
i
和人
j
互不認識 (vi, vj)E
說明此函數f polynomial time computable
{ 因為轉換後的圖G=(V,E),是以相鄰矩陣表示,該矩陣的大小為 |V|
2
。若要
將該矩陣填滿值則需時 O(|V|
2
)
{ ∴函數fPolynomial time computable
說明該函數f(x)使得對所有x而言,xL1 f(x)L2
{ 有三人互相認識 有一個三角形在圖形G
{ (証明):人
I
和人
j
和人
k
互相認識 vi vjvk兩兩有邊相連 vi vj
vk形成三角形
{ (証明)(理由同上)
I
和人
j
和人
k
互相認識
Q1
Q1
Q2
Q2
得証
得証
此函數為一個虛的轉換概念
35
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
P:
是一群Decision Problem的集合,這些問題皆可利用Deterministic
AlgorithmWorst Case的情況下,在
Polynomial Time
Polynomial Time的複雜度內
被解決
被解決
NP:
所謂 “NP” 是指Non-deterministicPolynomial兩個單字的簡寫
這類的問題只要給個解答,可以在Polynomial Time的複雜度內很快
驗證
驗證
(Verify)
(Verify) 出這個解答是否正確。
{ 由於決定性演算法為非決定性演算法的一個特例,且容易找到答案也
會容易驗証答案。因此,P可視為NP的一個特例。
{ PNP (
9
9)
{ P=NP (
?
?)
P, NP, NP hard, NP complete
36
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
NP-hard:
是一群Decision Problem的集合。當 Q NP-hard 若且唯若所有屬
NPDecision Problem Q’ (Q’NP) 皆可
多項式時間轉化
多項式時間轉化Q
(Q’Q)
此類問題至今仍未找到一個多項式複雜度的決定性演算法,且一
般相信沒有多項式複雜度的決定性演算法存在。
NP-complete:
是一群Decision Problem的集合。 若某一個問題Q屬於NP-
complete,則滿足以下兩個條件:
{ Q屬於
NP
NP
{ Q屬於
NP
NP
-
-
hard
hard
37
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
一般而言,理論學家相信上述問題之集合圖示如下:
NP-hardNP-complete的關係:
所有NP-complete問題都是NP-hard問題 (如:旅行推銷員問題)
但是NP-hard問題不見得是NP-complete問題 (如:程式停止問
題,它不是NP問題)
NP-complete NP-hard
如果有一個NP-hard問題能夠找到多項式複雜度的決定性演算法,
則所有NP-complete問題也都存在多項式複雜度的決定性演算法。
NP NP-hard
P
NP-
complete
38
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Nearly all of the decision problems are NP problems.
In NP problems, there are some problems which have
polynomial algorithms
polynomial algorithms
. They are called
P problems
P problems.
Every
Every
P problem
P problem
must be an NP problem
must be an NP problem.
There are a large set of problems which, up to now, have
no
no
polynomial algorithms
polynomial algorithms.
Summary
39
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Some important properties of
NP
NP
-
-
complete problems
complete problems:
Up to now, no NP-complete problem has any worst case polynomial
algorithm.
If any NP-complete problem can be solved in polynomial time,
NP = P
NP = P.
If
the
the
decision version of an optimization problem
decision version of an optimization problem
is NP
is NP
-
-
complete
complete,
this
optimization problem
optimization problem is called
NP
NP
-
-
hard
hard
.
We can conclude that all
We can conclude that all
NP
NP
-
-
complete
complete
and
and
NP
NP
-
-
hard
hard
problems must be
problems must be
difficult problems
difficult problems
because
They do not have polynomial algorithms at present.
It is quite unlikely that they can have polynomial algorithms in the future.
40
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
如何証明某個問題為NP-complete問題
証明某問題為NPC的理由:
所有的NP-complete問題都是具有相關性的
因此,若有一個NP-complete問題能夠找到多項式複雜度的決定性
演算法來解它,若且唯若所有NP-complete問題也都存在多項式複
雜度的決定性演算法。
証明方法:欲証明QNPC,則有以下兩個步驟:
c 証明QNP (can guess an answer, and check it in polynomial time)
d 找一個已知的NPC問題 Q’ 証明Q’Q (即:証明QNP hard)
{ 存在一個函數f(x)
{ 此函數f(x)polynomial-time computable
{ 該函數f(x)使得對所有x而言,xL1 若且唯若 f(x)L2
(L1Q’問題的解集合;L2Q問題的解集合)
(簡單)
(複雜)
41
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
為什麼經由前面兩步驟就可以証明QNPC
理由:
步驟 1 主要在說明Q是屬於NP問題
步驟 2 主要在說明Q是屬於NP-hard問題
{ 因為一個NP-complete問題,它既是屬於NP問題、也是屬於NP-hard
問題。假若 Q’ 為一個已知的NP-complete問題,因此 Q’ 既是屬於NP
問題,也應該屬於NP-hard問題。
{ 因為 Q’ NP-hard問題的血統,因此我們可以得知所有的NP問題
Q’(NP-hard的定義得知)
{ 由於 所有的NP問題 Q’ ”。若我們能夠証明出Q’Q,根據
遞移性,就可以得知所有NP問題 Q (所有NP問題 Q’
Q)。因此 Q 即屬於NP-hard問題。
Q如果既是屬於NP問題,也是屬於NP-hard問題,則Q即屬於
NP
NP
-
-
complete
complete
問題
問題
42
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
問題:
如果每一個NP-Complete的問題都可以由另一個已知的
NP-Complete問題所推導而得,那麼:
全世界第一個NP-Complete問題是誰?
43
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
庫克定理 (Cook’s Theorem)
SAT問題屬於NP-Complete (即:SATNPC)
如果有一個多項式時間的演算法可以解決SAT問題,則
所有屬於NP的問題都可以在多項式時間內解決
SAT是全世界第一個被很辛苦地証明出來的NPC問題
往後的學者所証明出之NPC問題,皆是藉由該定理所陸
續推導出來
44
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
後續NPC問題大致的推衍流程如下圖 (各家版本不一)
45
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
証明下列定理:
3-SAT問題為NP-Complete
Clique (結黨) 問題為NP-Complete
Vertex-Cover (頂點覆蓋) 問題為NP-Complete
46
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
証明定理:3-SAT問題為NP-Complete
何謂3-SAT問題:
SAT問題的特定型態。給一個SAT函數,且此函數中每一個括號
內皆恰有3個變數
,則我們對存在於此函數中的一些變數分別指派
TrueFalse,使這個函數結果為True
Ex: Let E = (-x
1
x
2
-x
3
)(x
1
-x
2
-x
4
) (-x
5
x
2
x
3
). Then the
following assignment will make E true and the answer will be “
yes
yes”.
x
1
T, x
2
T, x
3
T, x
4
F, x
5
F
【証明方法】欲証明QNPC,則:
証明QNP (can guess an answer, and check it in polynomial time)
找一個已知的NPC問題 Q’,証明Q’Q
{ 存在一個函數f(x)
{ 此函數f(x)polynomial-time computable
{ 該函數f(x)使得對所有x而言,xL1 若且唯若 f(x)L2
47
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
重點:Can guess an answer, and check it in polynomial time
証明:給一個具CNF型式且每一個括號內恰含3個變數的布林函數。當
給定(猜出)一組解時,則可在Polynomial Time內驗証是否可使該函數
為true。3-SATNP
由以下的非決定性演算法得知此問題在猜一組解答僅需O(n),而驗証
解答僅需常數時間O(c)。由於可在Polynomial Time的複雜度內很快地
驗證出解答是否正確,故得知此問題為NP問題。
/*
Guess
*/
for i = 1 to n do
x
i
← choice(true, false);
/* Verification
*/
if E(x
1
, x
2
, ,x
n
) is true then
success;
else failure.
証明QNP
48
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
証明Q’Q
SAT問題是一個已知的NPC problem (by 庫克定理)。因此,我們
令它為Q’,而待驗証的3-SAT問題為Q
証明Q’Q即是說明下列三個事項:
是否存在一個函數f(x),可以將Q的問題型態轉換成Q的問題型態
此函數f(x)是否為polynomial-time computable
該函數f(x)是否對所有x而言,xL1 f(x)L2
(L1Q’問題的解集合;L2Q問題的解集合)
49
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
【說明事項 1是否存在一個函數f(x)
給定一個SAT問題的布林函數E,試著將此函數 E 轉換成每個括號內的變數
個數均恰有三個之新的布林函數 E’,且此新函數 E’ 不能變更原函數 E 的邏
輯意涵。若能成功轉換,則表示 Q’ Q 之間確實存在一個函數 f(x)
由上表得知,Q’Q之間確實存在一個函數f(x)
變數個數
函數 E 括號內情況 轉換後之函數 E’
括號情況
1
(x
1
)
(x
1
y
1
y
2
)
(x
1
ӯ
1
y
2
)
(x
1
y
1
ӯ
2
)
(x
1
ӯ
1
ӯ
2
)
2
(x
1
x
2
)
(x
1
x
2
y
1
)
(x
1
x
2
ӯ
1
)
3
(x
1
x
2
x
3
)
不需做轉換
多於3
(x
1
x
2
x
k
)
(x
1
x
2
y
1
)
(ӯ
1
x
3
y
2
)
(ӯ
2
x
4
y
3
)
(ӯ
k-4
x
k-2
y
k-3
)
(ӯ
k-3
x
k-1
x
k
)
50
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
【說明事項 2此函數f(x)是否為polynomial-time computable
假設一個 SAT 問題的布林函數 E n 個括號,且每個括號中最多有 k
變數,則函數 E 轉換成 3-SAT 問題之布林函數 E’ 所花費的時間複雜度最
多只需要 O(nk)
SAT問題的布林函數 E 中,某一個括號內的變數:
{ 若只有一個或兩個變數時,則所需的轉換時間為常數時間 (∵轉換過程固定不
)
{ 若有三個變數時,則不需要轉換時間,轉換時間為 0
{ 若有多於三個變數 (即:k > 3) 時,則需要的轉換時間函數 k-2 (∵若一個clause
有k個變數,則會轉換出k-2個clause),時間複雜度為O(k)
由於可能有n個括號,因此所需要花費在轉換上的時間複雜度最多為 O(nk)
由上述說明,可得知
此函數
此函數
f(x
f(x
)
)
polynomial
polynomial
-
-
time computable
time computable
51
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
【說明事項 3此函數f(x)對所有x而言,xL1 若且唯若 f(x)L2
(註:L1Q’問題的解集合;L2Q問題的解集合)
以本題來說,要証明 有一組解可使SAT問題的布林函數 E True 有一
組解可使 3-SAT 問題的布林函數 E’ True”
(E is satisfiable
E
is satisfiable
)
c 【先証 E is satisfiable E is satisfiable
{ 若要讓一個SAT問題的布林函數 E True,則每一個括號均要為True
{ 若要讓一個括號為True,則此括號中至少要有一個變數為True
{ 若有一組可讓原SAT問題之布林函數 E True的解,也能使轉換後的3-SAT問題
之布林函數 E’ True,則該組解能讓 E’ 中的每一個括號均能夠為True
{ 將原本在SAT問題內為True x
i
變數所在的括號內的 y
i
變數設成False;原本在
SAT問題內為False之變數所在的括號內的 y
i
變數設成True,則此組解可使 E’
True
E is True
Eis True
52
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
d 【再証 E is satisfiable E is satisfiable
{ 若要讓一個3-SAT問題的布林函數 E’ True,則每一個括號均要為True
{ 若要讓一個括號為True,則去除掉 y
i
變數不看,此括號中至少要有一個x
i
數為True
{ 若有一組可讓原3-SAT問題之布林函數 E’ True的解,也必能使SAT問題之布
林函數 E True
c d 的証明,可以得知 有一組解可使SAT問題的布林函數 E 滿足
有一組解可使 3-SAT 問題的布林函數 E’ 滿足
由前面一系列說明,我們可以得知
SAT
SAT
3
3
-
-
SAT
SAT (Q’ Q)
更進一步地,我們可以得知
3
3
-
-
SAT
SAT
問題
問題
NP
NP
-
-
Complete Problem
Complete Problem
Eis True
E is True
53
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
証明定理:Clique問題為NP-Complete
【証明方法】欲証明Clique NPC,則:
証明CliqueNP
找一個已知的NPC問題 Q’,証明Q’Clique
{ 存在一個函數f(x)
{ 此函數f(x)polynomial-time computable
{ 該函數f(x)使得對所有x而言,xL1 若且唯若 f(x)L2
証明CliqueNP
給一個無向圖G = (V, E)。當給定(猜出)一組大小為k的頂點集合時,
則可在Polynomial Time驗証出此組頂點集合是否為該圖形G
Size kClique(by 相鄰矩陣來驗証)CliqueNP
54
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
找一個已知的NPC問題 Q,証明QClique
令此已知的NPC3-SAT Problem
存在一個函數f(x)
{ 給定一個具有kClause、且滿足3-SAT要求的布林函數F,透過以下
轉換步驟可將其變成一個無向圖G,且該圖G具有頂點個數k
Clique,以(G, k)表示。
對於F中的每一個Clause,建立一組頂點(Vertex),並依該Clause的變數
名稱來標示之。
建立頂點間的Edge。連線標準:同組不相連、矛盾不相連,其餘全部相
連。
(G, k)中的k = F的Clause個數
55
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
{ Ex:有一個布林函數F如下:
透過上述步驟,可畫出如下的圖。
上述過程可在Polynomial Time內做轉換
{ F轉為圖形G時,可用相鄰矩陣(Adjacency Matrix)表示圖形G
{ 此相鄰矩陣大小為3n × 3n,其中nClause個數,3表示每個Clause
3個變數。
{ 故建立此圖形G僅需O(n
2
)
)()()( zyxzyxzyxF
=
圖形G中,k=3的Clique
56
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
FSatisfiable GSize kClique
{ (由左往右)
假設有一組解A令函數FTrue,則A必使F中的每個ClauseTrue
每個ClauseTrue,則各個Clause內至少會有一個變數為True,且這些變
數必不會相互矛盾
這些為True的變數所對應的圖形G中之頂點,在G中必兩兩有邊相連
{ (由右往左)
假設在圖形G中有一個頂點集合C存在,且此集合C為圖GClique,則此
集合C中的頂點必無兩個頂點位在同一組
;且每組必有一頂點在C
令集合C中每個頂點所對應的變數為True,則可使布林函數F中的每個
Clause均有變數為True
F
F
Satisfiable
Satisfiable
由前面一系列說明,我們可以得知
3
3
-
-
SAT
SAT
Clique
Clique
更進一步地,我們可以得知
Clique
Clique
問題
問題
NP
NP
-
-
Complete
Complete
Problem
Problem
57
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
証明定理:Vertex Cover問題為NP-Complete
【証明方法】欲証明Vertex Cover NPC,則:
証明Vertex CoverNP
找一個已知的NPC問題 Q’,証明Q’Vertex Cover
{ 存在一個函數f(x)
{ 此函數f(x)polynomial-time computable
{ 該函數f(x)使得對所有x而言,xL1 若且唯若 f(x)L2
証明Vertex CoverNP
給一個無向圖G = (V, E)。當給定(猜出)一組大小為k的頂點集合時,
則可在Polynomial Time驗証出此組頂點集合是否為該圖形G
Vertex Cover(by 相鄰矩陣來驗証)Vertex CoverNP
58
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
找一個已知的NPC問題 Q,証明QVertex Cover
令此已知的NPCClique Problem
存在一個函數f(x)
{ (G, k) Clique的一個實例,則 Vertex Cover的一個實
例。
{ Ex:
G
此函數可以在Polynomial Time內,將 G 轉成
{ 即:將相鄰矩陣內的值做0/1互換,可在O(n
2
)內轉換完成。
k)n,G(
a
b
c
d
e
k = 3 Clique = {a, c, e}
G
a
b
c
d
e
n-k = 2 VC = {b, d}
G
59
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
GSize kClique Size n-kVertex Cover
{ (由左往右)
假設有一個頂點集合C為圖形G Clique,此集合C的所有頂點G中則
兩兩有邊存在。而集合C的所有頂點在 則彼此無邊。
集合C中的頂點於圖形 中若有邊存在,則該邊的另一頂點必位於V-C
的集合中。
由於集合V-C中所有的頂點會連接圖形 的所有邊,因此頂點集合V-C
為的Vertex Cover
{ (由右往左)
假設在圖形 有一個頂點集合D存在並為該圖形的Vertex Cover,則此
集合D中的頂點與圖形 所有的邊相連
頂點集合V-D在圖形 中彼此無邊存在,則必在圖形G中有邊相連。因
此,頂點集合V-D為圖形 G Clique
由前面一系列說明,我們可以得知
Clique
Clique
Vertex Cover
Vertex Cover
更進一步地,我們可以得知
Vertex Cover
Vertex Cover
問題
問題
NP
NP
-
-
Complete
Complete
Problem
Problem
G
G
G
G
G
G
G
G
60
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
近似演算法 (Approximation Algorithm)
一個問題Q若屬於NP-complete問題,則代表此問題目前尚無有效率的
演算法可以解決(即:目前無法在Polynomial Time內找出最佳解) 。更
甚者,若是NP-hard問題,大概可以確定找不到有效率的演算法來解
決它了。
然而,許多NP-complete/NP-hard的問題卻常常出現在各種領域!!若我
們退而求其次,去找尋一個
近似解
近似解而非最佳解的話,則能夠預期以有
效率的方式解決此問題。此即Approximation Algorithm的精神。
設計一個近似演算法需注意的Issue:
需保証近似演算法所求出的解也是該問題的可行解
近似演算法的時間複雜度要很低 (至少要為Polynomial Time)
用近似演算法所求出之近似可行解在最差的情況下之品質衡量,即:用近
似演算法求出來的解有多靠近最佳解
61
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Approximation Ratio
Approximation Ratio用來定義所求出之可行解有 多靠近
最佳解:
對於某個問題而言,在給定輸入為x之情況下,令其最佳解為
Opt(x),而利用近似演算法A所求出的解為A(x)。若此近似演算法A
為ε-approximation,則滿足:
其中,ε稱為近似演算法的Approximation Ratio
某問題的
近似解
近似解,與
最佳解
最佳解之間的差距
不會超過
不會超過
(
(
或低於
或低於
)
)
ε
ε
上述不等式中的max是為了同時考量最小化與最大化問題的應用。
x. allfor ,)
A(x)
Opt(x)
,
Opt(x)
A(x)
max(
ε
62
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
上述定義同時針對
最大化
最大化
最小化
最小化問題之解做考量。
若是
最小化問題
最小化問題,則 會比 大,因此 為該問題
Approximation ratio。此時,前述定義的不等式變為:
若是
最大化問題
最大化問題,則 會比 大,因此 為該問題
Approximation ratio。此時,前述定義的不等式變為:
Opt(x)
A(x)
Opt(x)
A(x)
A(x)
Opt(x)
A(x)
Opt(x)
Opt(x)
A(x)
A(x)
Opt(x)
x.allfor ,
Opt(x)
A(x)
ε
x.allfor ,
A(x)
Opt(x)
ε
63
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Ex. 1: Vertex-Cover Problem有一個近似演算法如下。此演算
法保証每次找到的解為一個Vertex Cover,且大小最多只比
最佳解多兩倍。
Input: G=(V, E)
Output: G的一個Vertex Cover C
Approx-VC(G)
C←∅;
EE;
while (E)
{令(u, v)為E中的任一邊;
將頂點u和v加入集合C中;
去掉E中所有與頂點u和v相連的邊;
}
1
2
3
4
5
6
例如:給定以下之無向圖,
c
d h
ge
f
i
最佳解Opt = {d, f, h}
近似解C = {c, d, e, f, g, h}
8
8
8
8
8
8
8
8
64
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
分析: (by近似演算法需注意的三個Issue)
近似演算法所求出的解也是該問題的可行解
{ while迴圈中,line 4於每一回合會挑選出一個邊 ,並會在line 5中將
此邊的兩個頂點(u, v)加入集合C中,而line 6會刪除被uvcover
的邊。
{ 也就是說,每一回合自E’刪除的邊均被集合C中的頂點所cover到,而
存留在E’的邊則是未被集合C中之頂點所cover
{ 因此,當E’為空集合時,表示C中所有的頂點會cover圖中所有的邊。
集合C是一個Vertex Cover
近似演算法的時間複雜度要很低
{ 演算法中的while迴圈最多跑|E|回合,故時間複雜度為O(|E|)
品質衡量
65
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
品質衡量 (續前)
{ 令集合Opt為最佳解的頂點集合 (即:Vertex Cover的規模最小),集合
A為每回合由line 4所挑選的
所構成之集合。
{ 由於line 5會將每個回合於line 4所挑出來的邊之兩個頂點加入到集合C
中,因此可以得知|C|=2|A|
{ 由於line 4在各個回合所挑出來的邊,彼此間不會有共同的vertex。因
此,在最佳解集合Opt裡,至少會包含集合A中的每條邊之12
vertex (否則Opt內的頂點就無法cover集合A中,沒有被包含到的那些
!!)。所以|Opt||A|
{ 綜合上面所述,可以得到 |C |=2|A| 2|Opt| Ö |C | 2|Opt| 。因此,
approximation ratio2
66
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Ex. 2TSP最佳化問題為NP-complete問題。課本上提出兩個
解該問題的近似演算法。
[
[
Algo
Algo
. 1]
. 1]
此近似演算法的解與最佳解之差距 (定理9.6)minapprox
< 2 ×
mindist
[
[
Algo
Algo
. 2]
. 2]
此近似演算法的解與最佳解之差距 (定理9.7)minapprox2 < 1.5
×
mindist
67
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
補充
68
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
▓各類問題的說明
SAT Problem (The Satisfiability Problem; 滿足問題):
給一個具CNF型式的布林函數E,判斷是否存在一組解,使得此函
數為True。若存在則稱此函數為Satisfiable。
{ CNF (Conjunction Normal Form)型式:括號內的變數皆以or運算 ()
相連,而括號間則以and運算()相連的函數型式稱之。
Ex:
{ Let E = (-x
1
x
2
-x
3
)(x
1
-x
2
) (x
2
x
3
). Then the following
assignment will make E true, and the answer will be
yes
yes.
x
1
F, x
2
F, x
3
T
{ If E = (-x
1
x
1
) , there will be no assignment which can make E true,
and the answer will be
no
no.
此問題為第一個被証明是屬於
NP
NP
-
-
Complete
Complete的問題 (by S. A. Cook,
1971).
69
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
3-SAT Problem (Three Variables SAT Problem):
給予一個具CNF型式的布林函數,且其中每組Clause(和項)都只包
含三個變數,判斷是否存在一組解,使得此函數為True
。若存在
則稱此函數為Satisfiable。
{ E = (-x
1
x
2
-x
3
)(x
1
-x
2
-x
3
) 為3-SAT
{ E = (-x
1
x
2
-x
3
)(x
1
-x
2
) 不為3-SAT
70
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Clique (結黨; 派系)
一個無向圖 (Undirected Graph) G = (V, E)中,存在一個子圖
(Sub-graph) G,且此子圖G為一個完整圖 (Complete Graph),則
G的頂點集合即為G的Clique。
{ Complete Graph:
一個 任兩個頂點間皆有一個邊相連之圖形稱之。
即:當一個Complete Graph有n個頂點時,該圖形的邊之個數共
n(n-1)/2條。
Clique Problem:
給予一個Undirected Graph G及一個整數 k (其中k>0),判斷在G
中是否可找到一個頂點個數k的Clique。
71
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Ex:有一圖形G如下:
請問在G中是否可找到一個頂點個數3的Clique?
Ans: 可以
Clique
Not Clique
72
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
Vertex-Cover (頂點覆蓋)
一個圖形G的Vertex Cover為一組頂點集合C.
圖形G中每個邊所相連的兩個頂點(u, v),至少會有一個位於此頂
點集合C當中。表示這個頂點集合C可以Cover圖形G中所有的邊。
Ex:
{a, d, e}為此圖的Vertex Cover
Vertex Cover Problem:
給予一個無向圖G與一個整數k,判斷在圖形G中是否可找到一個
頂點個數k的頂點集合C,使得G中所有的邊皆至少有一個相連頂
點位於此集合C中。
a
b
c
d
e
f